package binaryTree;

import java.util.LinkedList;
import java.util.Optional;
import java.util.Queue;

public class IsSameTree {

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p==null&&q!=null||q==null&&p!=null){
            return  false;
        }
        if (p==null&&q==null){
            return true;
        }
        if (p.val!=q.val){
            return  false;
        }
        boolean sameTree1 = isSameTree(p.left, q.left);
        boolean sameTree2 = isSameTree(p.right, q.right);
        return   sameTree1&&sameTree2;
    }

    public   boolean  isSameTree1(TreeNode p,TreeNode  q){
        Queue<TreeNode>  que1 = new LinkedList<>();
        Queue<TreeNode>  que2 = new LinkedList<>();
        que1.add(p);
        que2.add(q);
        while (!que1.isEmpty()||!que2.isEmpty()){
            if (que1.isEmpty()&&!que2.isEmpty()||!que1.isEmpty()&&que2.isEmpty()){
                return false;
            }
            TreeNode cur1 = que1.poll();
            TreeNode cur2 = que2.poll();
            if (cur1==null&&cur2==null){
              continue;
            }
            if (cur1==null&&cur2!=null||cur2==null&&cur1!=null||cur1.val!=cur2.val){
                return  false;
            }
                que1.add(cur1.left);
                que1.add(cur1.right);
                que2.add(cur2.left);
                que2.add(cur2.right);


        }
        return true;



    }

    public static void main(String[] args) {


        TreeNode root= new TreeNode(1);
        TreeNode treeNode1 = new TreeNode(2);
        root.left=treeNode1;

        TreeNode root1= new TreeNode(1);
        TreeNode treeNode11 = new TreeNode(2);
        root1.right=treeNode11;

        IsSameTree isSameTree = new IsSameTree();

        System.out.println(isSameTree.isSameTree1(root, root1));




    }

}


